import java.util.PriorityQueue;

class MedianFinder {
    private final PriorityQueue<Integer> left = new PriorityQueue<>((a, b) -> b - a); // 最大堆
    private final PriorityQueue<Integer> right = new PriorityQueue<>(); // 最小堆

    public MedianFinder() {

    }

    public void addNum(int num) {
        if (left.size() == right.size()) {
            //无论 num 是大是小，都可以先把 num 加到 right 中，
            //然后把 right 的最小值从 right 中去掉，并添加到 left 中。
            right.offer(num);
            left.offer(right.poll());
        } else {
            //无论 num 是大是小，都可以先把 num 加到 left 中，
            //然后把 left 的最大值从 left 中去掉，并添加到 right 中。
            left.offer(num);
            right.offer(left.poll());
        }
    }

    public double findMedian() {
        if (left.size() > right.size()) {
            return left.peek();
        }
        return (left.peek() + right.peek()) / 2.0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */